package LinkedList.合并有序链表_k个;

import LinkedList.ListNode;

import java.util.PriorityQueue;

public class Test {
    public ListNode mergeKLists(ListNode[] lists) {
        // 将每个链表的头节点插入优先队列
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
        for(ListNode node : lists) {
            if(node != null) {
                queue.offer(node);
            }
        }

        // 创建一个虚拟头节点用于方便操作
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        // 逐个从优先队列中取出最小节点并处理
        while (!queue.isEmpty()) {
            ListNode minNode = queue.poll();
            cur.next = minNode;
            cur = cur.next;

            // 如果当前节点的下一个节点不为空，将其加入优先队列
            if(minNode.next != null) {
                queue.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}
